package basic.sort.tree;

import basic.sort.utils.NodeUtil;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.tree
 * @since JDK1.8
 *
 * 一个树上，节点可以向下也可以向上。
 * 而两个节点路径上节点的数量就是这两个节点的距离
 *
 * 有两种大情况：
 *      节点X参与：
 *          求出左子树的最大距离和右子树的最大距离
 *      节点X不参与：
 *          则距离为左子树的高加上右子树的高再加1
 */
public class MaximumDistance {

    private static class Info {
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    private static int maxDistance(NodeUtil head) {
        return process(head).maxDistance;
    }

    private static Info process(NodeUtil head) {
        if (head == null) {
            return new Info(0, 0);
        }

        // 获取左右子树的信息
        Info left = process(head.left);
        Info right = process(head.right);

        // 分别获取左右子树的最大距离和左右子树的高度和再加1
        int p1 = left.maxDistance;
        int p2 = right.maxDistance;
        int p3 = left.height + right.height + 1;

        // 求此节点的最大距离和其高度
        int maxDistance = Math.max(Math.max(p1, p2), p3);
        int height = Math.max(left.height, right.height) + 1;

        // 返回信息
        return new Info(maxDistance, height);
    }
}
